package com.hdu.hot100.heap;

import java.util.*;

public class lc347 {
    class Solution {
        public int[] topKFrequent(int[] nums, int k) {
            Map<Integer, Integer> num2freq = new HashMap<>();
            for (int num : nums) {
                num2freq.put(num, num2freq.getOrDefault(num, 0) + 1);
            }
            PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(num2freq::get));
            for (Integer key : num2freq.keySet()) {
                if (pq.size() < k)
                {
                    pq.offer(key);
                }
                else
                {
                    if (num2freq.get(key) > num2freq.get(pq.peek()))
                    {
                        pq.poll();
                        pq.offer(key);
                    }
                }
            }
            int[] ans = new int[k];
            for (int i = 0; i < k; i++) {
                ans[i] = pq.poll();
            }
            return ans;
        }
    }
}
